from typing import List


# 221. 最大正方形
def maximalSquare(matrix: List[List[str]]) -> int:
    m = len(matrix)
    n = len(matrix[0])
    # dp 数组
    dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    # 记录最大正方形的边长
    max_matrix = 0

    for row in range(1, m + 1):
        for column in range(1, n + 1):
            current_matrix = 0
            # 设置当前位置最大正方形的边长
            if matrix[row - 1][column - 1] == "1":
                last_level = dp[row - 1][column - 1]
                # 当前位置的起始边长
                current_matrix = 1
                if last_level > 0:
                    # 判断是否符合条件，符合条件，边长+1
                    for i in range(1, last_level + 1):
                        if matrix[row - 1 - i][column - 1] == "1" and matrix[row - 1][column - 1 - i] == "1":
                            current_matrix += 1
                        else:
                            break
                max_matrix = max(current_matrix, max_matrix)

            dp[row][column] = current_matrix

    # 返回边长的平方
    return max_matrix * max_matrix


matrix_1 = [["1", "1", "0", "1"],
            ["1", "1", "0", "1"],
            ["1", "1", "1", "1"]]
result = maximalSquare(matrix_1)
print(f"result:{result}")

matrix_1 = [["1", "0", "1", "0", "0"],
            ["1", "0", "1", "1", "1"],
            ["1", "1", "1", "1", "1"],
            ["1", "0", "0", "1", "0"]]
result = maximalSquare(matrix_1)
print(f"result:{result}")

matrix_1 = [["0", "1"],
            ["1", "0"]]
result = maximalSquare(matrix_1)
print(f"result:{result}")

matrix_1 = [["0"]]
result = maximalSquare(matrix_1)
print(f"result:{result}")

matrix_1 = [["1", "1", "0", "0", "0"],
            ["1", "1", "1", "0", "0"],
            ["0", "1", "1", "1", "0"],
            ["0", "0", "1", "1", "1"],
            ["0", "0", "0", "1", "1"]]
result = maximalSquare(matrix_1)
print(f"result:{result}")

matrix_1 = [["1", "1"],
            ["1", "1"]]
result = maximalSquare(matrix_1)
print(f"result:{result}")
